googologywikiaorg-20200223-history
Forum:Is my notation as powerful as array notation?
Hey. Newb here. I wanted to see how far I could go by developing my own notation from scratch. Not to set any records, just for fun. I kept adding more and more levels of recursion, then realized it could all be described by a simple set of rules. The rules actually seem very similar to array notation... I think it's about as powerful, but I'm not totally sure. Anyone want to weigh in? I call it "bar notation", because it makes heavy use of vertical bars (|||). I've also defined a more powerful extended notation, but I wanted to see how this notation stacks up to the others first. The rules are like this: A chain is a list of 1 or more nonnegative integers (terms) seperated by bars, with a leading bar, ex: |2|0|71|9, |4, ' |3|68', etc. Any leading zeros in a chain with length > 1 are immediately discarded (unless the zero is the chain's only term), ex: |0|0|5|0|1 = |5|0|1 Chains can be assigned to variables- a chain variable is prefixed with a tilde (~), ex: ~x, ~a, ~thisIsAChain, etc Chains can be decremented with the -- operator. Decrementing a chain will subtract one from the farthest right nonzero element of the chain. ex:' |2|0|0-- = |1|0|0', ' |3|4-- = |3|3', if we let ~x = |2|2 then ~x-- = |2|1, etc. Every chain can also be used as a function, ex.' |3|6|3(9,1)' , ~n(2,6) You could say chains ARE functions. When used as a function, a chain takes exactly 2 arguments. The result of the function is specified by these rules: |0(x,y) = x+1 '(if a chain only contains a zero, then it returns it's first argument + 1) '|a|0|0|0...{e "|0"s}...|0|0 (x,y) = |a-1|x|x|x...{e "|x"s}...|x|x(x,x) (If a chain is made of a leading nonzero term followed by all zeros, the 0's are replaced by x''' and the leading term is decremented, then this new chain is applied as a function to the arguments (x,x)' ) if neither of the above cases hold, '~n(x,1) = ~n--(x,x)' '~n(x,y) = ~n(~n--(x,x), y-1)' where '~n''' is any arbitrary chain. That's enough to fully describe my notatation. But I didn't develop it by just sitting down and writing out the rules. I started with |'0(x,y)', then defined |1, |2, and others recursively in terms of it. Only after I made it all the way to |d|c|b(x,y) did I realize that it could all be described by a general rule. To better understand how the notation works, it helps to forget about the general ruleset, and start with |0 and define all others in terms of it, as I did originally (if you already understand it, you don't have to read anything after this). ' |0(x,y): x+1' |1 can be defined recursively in terms of |0 ' (the // at the end of a line indicates a comment describing the function in terms of standard arithmetic operators, and has nothing to do with the function definition) '|1(x,1): |0(x,x) //x+1 |1(x,a): |1(|0(x,x), a-1) //x+a |2 can be defined in terms of''' |1''' |2(x,1): |1(x,x) //x*2 |2(x,a): |2(|1(x,x), a-1) //x*2^a ... and so on for any |b. The general rule is: |0(x,y): x+1 |b(x,1): |b-1(x,x) ' '|b(x,a): |b(|b-1(x,x), a-1) Now we'll define |1|0 |1|0(x,y): |x(x,x) //I believe this is roughly equivalent to the Ackermann function Similar to |b, we can define |1|b for any b', using the general rule: '|1|b(x,1): |1|b-1(x,x) ' '|1|b(x,a): |1|b(|1|b-1(x,x), a-1) ' Then we could go on to define '|2|b from |1|b, in the same way''' |1|b''' was defined from |b. Then |3|b, and so on. But instead of defining each one individially, we'll make a general rule for any |c|b: |c|0(x,y): |c-1|x(x,x) |c|b(x,1): |c|b-1(x,x) |c|b(x,a): |c|b(|c|b-1(x,x), a-1) Then we can define |d|c|b. If we write out a set of rules for every case. it would look like this: |d|0|0(x,y): |d-1|x|(x,x) |d|0|b(x,1): |d|0|b-1(x,x) |d|0|b(x,a): |d|0|b(|d|0|b-1(x,x), a-1) |d|c|0(x,1): |d|c-1|0(x,x) |d|c|0(x,a): |d|c|0(|d|c-1|0(x,x), a-1) |d|c|b(x,1): |d|c|b-1(x,x) |d|c|b(x,a): |d|c|b(|d|c|b-1(x,x), a-1) But instead of writing all those rules out, it's easier to note that whenever c''' or '''b are nonzero, we just carry over d''' unchanged, and the rules otherwise work the same as before. The only time '''d changes is when c''' and '''b are both zero. We could keep going for''' |e|d|c|b', '|f|e|d|c|b''', and so on, but at this point I realized there was a general rule for all chains, which is the ruleset I described towards the top of my post. KevinRSP (talk) 19:57, August 22, 2015 (UTC) :Yes, your bar notation does grow at the same rate as linear array notation. In fact, your notation is quite similar to the fast-growing hierarchy; we have \(|a(x,x) = f_a(x)\) and \(|b|a(x,x) = f_{\omega b + a}(x)\). After that, the two notations diverge slightly since you have \(c|0|0(x,x) = c-1|x|x(x,x)\) rather than \(c|0|0(x,x) = c-1|x|0(x,x)\), but they still stay quite close to each other. Deedlit11 (talk) 04:55, August 23, 2015 (UTC) :You know, you could have wrote this in a blog post. -- From the googol and beyond -- 18:43, August 24, 2015 (UTC)